4486. Чебурашка и крокодил Гена

Когда Чебурашке и крокодилу Гене нечего делать, они играют в разные интересные игры. Сегодня Гена придумал новую игру, которая, по его мнению, поможет Чебурашке выучить арифметику. Правила игры очень просты: Гена возьмет n дощечек, пронумерует их от 1 до n и напишет на них какие-то числа. После чего он будет говорить два числа l и r, а Чебурашка будет должен посчитать сумму всех чисел на дощечках с номерами от l до r.

Также, чтобы Чебурашка не выучил все возможные ответы, Гена иногда меняет некоторые числа на другие, а именно все числа на промежутке [l, r]. Он не хочет сильно думать, поэтому просто пишет на этих дощечках числа от 1 до r – l + 1 по порядку. Чебурашка пока не очень хорошо знает арифметику, поэтому просит Вас написать ему программу, которая поможет ему в этом.

Вход.  В первой строке находится количество дощечек n (1 ≤ n ≤ 10⁶). В следующей строке находится n чисел – начальные значения, написанные на дощечках (все числа не превышают 10⁹). Далее следует количество запросов m (1 ≤ m ≤ 10⁵). Затем идет m строк, первое число в строке – это вид запроса t (1 ≤ t ≤ 2).

· Если t = 1, то далее следуют два числа l и r. Вам надо посчитать сумму всех чисел на дощечках с номерами от l до r.

· Если t = 2, то далее следуют два числа l и r. Это означает, что на дощечках с номерами от l до r будут теперь числа от 1 до r – l + 1 соответственно.

Гарантируется, что все промежутки корректны. Нумерация дощечек начинается с единицы.

Выход. Для каждого запроса с номером 1 выведите сумму чисел на промежутке [l, r].

Пример входа	Пример выхода
5 5 3 2 4 5 5 1 1 5 1 2 3 2 1 5 2 2 5 1 1 5	19 5 11

РЕШЕНИЕ

структуры данных - дерево отрезков

Анализ алгоритма

Построим дерево отрезков, поддерживающее операцию суммирования. В каждой вершине (фундаментальном отрезке [a; b]) дополнительно будем хранить число left, означающее что она покрывает значения left, left + 1, …, left + b – a (изначально left равно нулю для всех отрезков).

Рассмотрим процедуру проталкивания, где отрезок запроса q(x,y) лежит в левом и правом сыне (x ≤ m < y). Тогда для левого сына установим left равным 1, а для правого значение left на 1 больше длины отрезка [x; m].

Если x ≥ m + 1 (отрезок запроса полностью лежит в правом поддереве), то значение left для левого и правого сына установим равным 1.

Пусть запрос q(x,y) покрывается набором фундаментальных отрезков [a₁, b₁], [a₂, b₂], …, [a_k, b_k]. Тогда значение left для отрезка [a_i, b_i] установим равным 1 + сумма длин всех отрезков [a_j, b_j], для которых j < i. Например, рассмотрим дерево построенное на отрезке [1..8], и запрос q(2, 7). Запрос покрывает следующие фундаментальные отрезки:

Пример

Реализация алгоритма

Объявим массив SegTree для хранения дерева отрезков.

#define MAX 1000010

struct node

{

long long summa;

int left;

} SegTree[4*MAX];

Построение дерева отрезков.

void build(int Vertex, int LeftPos, int RightPos)

{

if (LeftPos == RightPos)

SegTree[Vertex].summa = a[LeftPos];

else

{

int Middle = (LeftPos + RightPos) / 2;

build (2*Vertex, LeftPos, Middle);

build (2*Vertex+1, Middle+1, RightPos);

SegTree[Vertex].summa =

SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;

}

}

Сума чисел от a до b.

long long Sum(int a, int b)

{

return 1LL * (a + b) * (b - a + 1) / 2;

}

Проталкивание значения из вершины в сыновья.

void Push(int Vertex, int LeftPos, int Middle, int RightPos)

{

if (SegTree[Vertex].left)

{

SegTree[2*Vertex].left = SegTree[Vertex].left;

SegTree[2*Vertex].summa =

Sum(SegTree[2*Vertex].left,

SegTree[2*Vertex].left + Middle - LeftPos);

SegTree[2*Vertex+1].left =

SegTree[Vertex].left + Middle - LeftPos + 1;

SegTree[2*Vertex+1].summa =

Sum(SegTree[2*Vertex+1].left,

SegTree[2*Vertex+1].left + RightPos - Middle - 1);

SegTree[Vertex].left = 0;

}

}

Промежуток [Left; Right] заполняем значениями From, From + 1, From + 2, ….

void Update(int Vertex, int LeftPos, int RightPos,

int Left, int Right, int From)

{

if (Left > Right) return;

if ((LeftPos == Left) && (RightPos == Right))

{

SegTree[Vertex].left = From;

SegTree[Vertex].summa = Sum(From,From + Right - Left);

return;

}

int Middle = (LeftPos + RightPos) / 2;

int Mid = Middle - Left + 1;

Если отрезок запроса [Left; Right] полностью лежит в правом сыне [Middle + 1; RightPos], то правому сыну передаем значение From без изменений (Mid устанавливаем равным нулю).

if (Mid < 0) Mid = 0;

Push(Vertex,LeftPos,Middle,RightPos);

Update(2*Vertex, LeftPos, Middle, Left, min(Middle,Right), From);

Update(2*Vertex+1, Middle+1, RightPos,

max(Left,Middle+1), Right, From + Mid);

SegTree[Vertex].summa =

SegTree[2*Vertex].summa + SegTree[2*Vertex+1].summa;

}

Возвращаем сумму чисел на интервале [Left; Right].

long long Summa(int Vertex, int LeftPos, int RightPos,

int Left, int Right)

{

if (Left > Right) return 0;

if ((LeftPos == Left) && (RightPos == Right))

return SegTree[Vertex].summa;

int Middle = (LeftPos + RightPos) / 2;

Push(Vertex,LeftPos,Middle,RightPos);

return Summa(2*Vertex, LeftPos, Middle, Left, min(Middle,Right)) +

Summa(2*Vertex+1, Middle+1, RightPos, max(Left,Middle+1), Right);

}

Основная часть программы. Читаем входной массив чисел. Строим дерево отрезков.

scanf("%d", &n);

for(i = 1; i <= n; ++i)

scanf("%d", &a[i]);

build(1, 1, n);

Последовательно обрабатываем q запросов.

scanf("%d", &q);

for(i = 0; i < q; ++i)

{

scanf("%d %d %d", &type, &l, &r);

if(type == 1)

printf("%lld\n", Summa(1,1,n,l,r));

else

Update(1,1,n,l,r,1);

}